<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>尾调用优化</title>
</head>
<body>
  <script>
    // 尾调用(Tail Call)是函数式编程的一个重要概念，本身非常简单，一句话就能说清楚，就是指某个函数的最后一步调用另一个函数。
    function f(x) {
      return g(x)
    }
    // 以下3种情况都不属于尾调用。
    // 情况一
    function f(x) {
      let y = g(x)
      return y // 调用完函数g后还有赋值操作，所以不属于尾调用。
    }
    // 情况二
    function f(x) {
      return g(x) + 1 // 调用后还有其余操作，也不属于尾调用
    }
    // 情况三
    function f(x) {
      g(x)
    }
    // 等同于
    function f(x) {
      g(x)
      return undefined
    }
    // 尾调用不一定出现在函数的尾部，只有是最后一步操作即可。
    function f(x) {
      if(x > 0) {
        return m(x)
      }
      return n(x)
    }
    // 上面代码中，函数m和n都属于尾调用，因为它们都是函数f的最后一步操作。
  </script>
  <script>
    /**
     * 尾调用之所以和其他调用不同，就在于它的特殊的调用位置。
     * 我们知道，函数调用会在内存形成一个调用记录，又称为“调用帧”(call frame),
     * 保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用帧上方，还会形成一个B的调用帧
     * 等到B运行结束，将结果返回到A，B的调用帧才会消失。如果在B的内部还调用函数C，就还有一个C的调用帧，以此类推。
     * 所有的调用帧，就形成一个“调用栈”(call stack)
     *
     * 尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用帧，因为调用位置、内部变量等信息都不会再用到了，
     * 只要直接用内层函数的调用帧，取代外层函数的调用帧就可以了。
    */
   function f() {
     var m = 1
     var n = 2
     return g(m+n)
   }
   f()
   // 等同于
   function f() {
     return g(3)
   }
   f()

   // 等同于
   g(3)
   /**
    * 上面代码中，如果函数g不是尾调用，函数f就需要保存内部变量m和n的值、g的调用位置等信息；
    * 但是由于调用g后，函数f就结束了，所以执行到最后一步，完全可以删除f(x)的调用帧，只保留g(3)的调用帧。
    * 这就叫做“尾调用优化”(Tail call optimization),即只保留内层函数的调用帧，如果所有函数都是尾调用，那么
    * 完全可以做到每次执行时，调用帧只有一项，这将大大节省内存。这就是“尾调用优化“的意义。
    * 注意：只有不再用到外层函数的内部变量，内层函数的调用帧才会取代外层函数的调用帧，否则就无法进行“尾调用优化”
   */
  function addOne(a) {
    var one = 1
    function inner(b) {
      return b + one
    }
    return inner(a)
  }
  /**
   * 上面的函数就不会进行尾调用优化，因为内层函数inner用到了外层函数addOne的内部变量one,
   * 注意，目前只有Safari浏览器支持尾调用优化，Chrome和Firefox都不支持。
  */
  </script>
  <script>
    // 尾递归
    // 函数调用自身，称为递归。如果尾调用自身，就称为尾递归。
    /**
     * 递归非常耗费内存，因为需要同时保持成千上百个调用帧，很容易发生“栈溢出”错误(stack overflow)
     * 但是对于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误
    */
    function factorial(n) {
      if (n === 1) return 1;
      return n * factorial(n - 1);
    }
    factorial(5) // 120
    // 上面代码是一个阶乘函数，计算n的阶乘，最多需要保存n个调用记录，复杂度O(n)
    // 如果改写成尾递归，只保留一个调用记录，复杂度O(1)
  </script>
  <script>
    function factorial(n, total) {
      if (n === 1) return total
      return factorial(n - 1, n * total)
    }
    var b = factorial(5, 1) // 120
    console.log(b)
    // => factorial(4, 5) => f(3, 20) => f(2, 60) => f(1, 120)
  </script>
  <script>
    // 还有一个比较著名的例子，就是计算Fibonacci数列，也能充分说明尾递归优化的重要性。
    // 非尾递归的Fibonacci数列实现如下。
    function Fibonacci(n) {
      if (n < 1 || n === 1) {return 1}
      return Fibonacci(n -1) + Fibonacci(n - 2)
    }
    Fibonacci(10) // 89
    // Fibonacci(100) // 超时
  </script>
  <script>
    // 通过尾递归优化Fibonacci数列实现
    function Fibonacci(n, ac1 = 1, ac2 = 1) {
      if (n < 1 || n === 1) return ac2
      return Fibonacci(n - 1, ac2, ac1 + ac2)
    }
    Fibonacci(100) // 573147844013817200000
    Fibonacci(1000)// 7.0330367711422765e+208
    Fibonacci2(10000) // Infinity
    /**
     * 由此可见，“尾调用优化”对递归操作意义重大，所有一些函数式编程语言将其写入了语言规格
     * es6也是如此，第一次明确规定，所有ECMAScript的实现，都必须部署“尾调用优化”，就这是说es6中只要使用尾递归，就不会发生栈溢出
     * (或者层层递归造成的超时)，相对节省内存。
    */
  </script>
  <script>
    /**
     * 尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。
     * 比如上面的例子，阶乘函数factorial需要用到一个中间变量total,那就把这个中间变量改写成函数的参数。
     * 这样做的缺点就是不够直观，第一眼很难看出来，为什么计算5的阶乘，需要传入俩个参数5 和 1？
     *
     * 俩个方法可以解决这个问题，方法一是在尾递归函数之外，再提供一个正常形式的函数。
     *
    */
   function tailFactorial(n, total) {
     if(n === 1) return total
     return tailFactorial(n - 1, n * total)
   }
   function factorial(n) {
     return tailFactorial(n, 1)
   }
   factorial(5)
   // 上面代码通过一个正常形式的阶乘函数factorial，调用尾递归函数tailFactorial看起来就正常多了。(其实也没多大用处，还是看不出来)
   /**
    * 函数式编程有一个概念，叫做柯里化(currying), 意思是将多参数的函数转换成单参数的形式。这里也可以使用柯里化。
   */
  function currying(fn, n) {
    return function (m) {
      return fn.call(this, m, n)
    }
  }
  function tailFactorial(n, total) {
    if (n === 1) return total
    return tailFactorial(n - 1, n * total)
  }
  const factorial = currying(tailFactorial, 1)
  factorial(5) // 120
  // 上面代码通过柯里化，将尾递归函数tailFactorial变为只接受一个参数的factorial.

  // 方法二，采用es6的函数参数默认值
  function factorial(n, total = 1) {
    if (n === 1) return total
    return factorial(n - 1, n * total)
  }
  factorial(5) // 120
  /**
   * 总结一下，递归本质上是一种循环操作，纯粹的函数式编程语言没有循环操作命令，
   * 所有的循环都用递归实现，这就是为什么尾递归对这些语言极其重要。对于其他支持
   * “尾调用优化”的语言(比如Lua, ES6)，只需要知道循环可以用递归代替，而一旦使用递归，就最好使用尾递归！！！
   *
   *
   * es6的尾调用优化只在严格模式下开启，正常模式是无效的。？？？？(好像正常模式也能用啊？？？)
   * 这是因为在正常模式下，函数内部有俩个变量，可以跟踪函数的调用栈。
   * func.arguments: 返回调用时函数的参数。
   * func.caller: 返回调用当前函数的那个函数。
   * 尾调用优化发生时，函数的调用栈会改写，因此上面俩个变量就会失真，严格模式禁用这俩个变量，所以尾调用模式仅在严格模式下生效。
  */
  </script>
  <script>
    // 尾递归优化的实现
    /**
     * 尾递归优化只在严格模式下生效，那么正常模式下，或者那些不支持该功能的环境中，有么有办法也使用尾递归优化呢？
     * 回答是可以的，就是自己实现尾递归的优化，它们的原理非常简单，尾递归之所以需要优化，原因是调用栈太多，造成溢出。
     * 那么只要减少调用栈，就不会溢出。怎么做可以减少调用栈呢？就是采用“循环”换掉“递归”
    */
   function sum(x, y) {
     if(y > 0) {
       return sum(x + 1, y - 1)
     } else {
       return x
     }
   }
   sum(1, 100000) // Uncaught RangeError: Maximum call stack size exceeded(…)
   //上面代码中，sum是一个递归函数，参数x是需要累加的值，参数y控制递归次数。一旦指定sum递归 100000 次，就会报错，提示超出调用栈的最大次数。
   // 蹦床函数(trampoline)可以将递归执行转为循环执行。
   function trampoline(f) {
     //while是用来做循环的，也就是说只要条件满足，就会执行一次循环体，执行完以后会再判断一次条件
     //  如果满足条件，还会再执行一次，终而复始，除非你在循环中对条件进行了改变才会从循环中跳出来。
     // 而if只做一次判断, 条件不满足就不执行，满足就执行一次，执行完就往下执行，不会再回过头来继续执行。
     while(f && f instanceof Function) {
       f = f() // 这里的f()每次都是一个新的函数 ！！
     }
     return f
   }
   /**
    * 上面就是蹦床函数的一个实现，它接受一个函数f作为参数，只要f执行后返回一个函数，就继续执行，
    * 注意，这里是返回一个函数，然后执行该函数，而不是在函数里面调用函数，这样就避免了递归执行。
    * 从而消除了调用栈过大的问题。然后，要做的就是将原来的递归函数，改写为每一步返回另一个函数。
    *
   */
  function sum(x, y) {
    if (y > 0) {
      return sum.bind(null, x + 1, y - 1) // 这里返回一个新的函数，this指向了null?
    } else {
      return x
    }
  }
  // 上面代码中sum函数的每次执行，都会返回自身的另一个版本。现在使用蹦床函数执行sum,就不会发生调用栈溢出。
  // trampoline(sum(1, 100000))
  var c = trampoline(sum(1, 100000))
  console.log(c) // 100001
  </script>
  <script>
    //蹦床函数并不是真正的尾递归优化，下面的实现才是
    function tco(f) {
      var value
      var active = false
      var accumulated = []
      return function accumulator() {
        accumulated.push(arguments)
        if(!active) {
          active = true
          while(accumulated.length) {
            value = f.apply(this, accumulated.shift())
          }
          active = false
          return value
        }
      }
    }
    var sum = tco(function(x, y) {
      if(y > 0) {
        return sum(x + 1, y - 1)
      }else {
        return x
      }
    })
    sum(1, 100000)
    /**
     * 上面代码中，tco函数是尾递归优化的实现，它的奥秘就在于状态变量active.
     * 默认情况下，这个变量是不激活的，一旦进入尾递归优化的过程，这个变量就激活了。
     * 然后，每一轮递归sum返回的都是undefined，所以就避免了递归执行；
     * 而accumulated数组存放每一轮sum执行的参数，总是有值的，这就保证了accumulator函数内部的while循环总会执行。
     * 这样就很巧妙地将递归改写成了循环，而最后一轮的参数会取代前一轮的参数，保证了调用栈只有一层。
    */
  </script>
</body>
</html>